package com.example.demo.tixiban;

/**
 * @author xujm
 * @version V2.4
 * 一个数组arr中， 有一个数出现了K次，其他数都出现了M次
 * 并且 1<K<M 那么求出现了K次的这个数的值
 * 要求空间复杂度O(1) 时间复杂度O(N)
 *
 * @since 2.4.0 2022/2/20 13:58
 */
public class Arr_一个数组中出现K次和M次的数 {

    /**
     * 思路:
     *  定义一个常数大小的数组 int [] t
     *  (1)遍历arr，将每个数每一位上的1都在 t 中对应的位置上加1
     *  举例: 1100 这个数， 应该 t[2]++ ,t[3]++
     *  (2)之后遍历 t 数组
     *   容易知道t上的各位 都是 0 或者 M  或者 K + M
     *   那么将t上的数 模 M ，如果不等于0，那么说明该位置被K的二进制占用过(假设这个位置是2)
     *   res += i<<2;
     *   举例:
     *   出现K次的数是 1100 ,出现M 次的数是 0110
     *   那么t[1] 是M,
     *   t[2] % M = K , 所以 2位置上存在过K次数
     *
     * @param arr
     * @return
     */
    public static int findKTimeValue(int [] arr,int k,int m){

        int [] t = new int [32];
        for(int num: arr){
            for(int j=0;j<t.length;j++){
                if(((num>>j) & 1) != 0){
                    t[j]++;
                }
            }
        }
        int res = 0;
        for(int i=0;i<t.length;i++){
            if((t[i] % m) !=0){
                res+=1<<i;
            }
        }
        return res;
    }

    public static void main(String[] args) {

        int [] arr = {3,3,5,5,5,5,12,12,12,12};
        System.out.println(findKTimeValue(arr,2,4));
    }

}
